use crate::hot100::base::{ListNode, Vec2ListNode};

#[test]
fn test_merge_two_lists() {
    let node = ListNode::new(0);
    assert_eq!(
        merge_two_lists(node.from_vec(vec![1, 2, 4]), node.from_vec(vec![1, 3, 4])),
        node.from_vec(vec![1, 1, 2, 3, 4, 4])
    );

    assert_eq!(
        merge_two_lists(node.from_vec(vec![]), node.from_vec(vec![])),
        node.from_vec(vec![])
    );

    assert_eq!(
        merge_two_lists(node.from_vec(vec![]), node.from_vec(vec![0])),
        node.from_vec(vec![0])
    );
}
/*
   21. 合并两个有序链表
   将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

   示例 1：
   输入：l1 = [1,2,4], l2 = [1,3,4]
   输出：[1,1,2,3,4,4]

   示例 2：
   输入：l1 = [], l2 = []
   输出：[]

   示例 3：
   输入：l1 = [], l2 = [0]
   输出：[0]

   提示：
   两个链表的节点数目范围是 [0, 50]
   -100 <= Node.val <= 100
   l1 和 l2 均按 非递减顺序 排列
*/
pub fn merge_two_lists(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut dummy = ListNode::new(0);
    let (mut l1, mut l2, mut p) = (l1, l2, &mut dummy);

    while let (Some(n1), Some(n2)) = (l1.as_ref(), l2.as_ref()) {
        if n1.val < n2.val {
            p.next = l1;
            p = p.next.as_mut()?;
            l1 = p.next.take();
        } else {
            p.next = l2;
            p = p.next.as_mut()?;
            l2 = p.next.take();
        }
    }
    p.next = l1.or(l2);

    dummy.next
}
